Content addressable memory (CAM) devices are frequently used in network switching and routing applications to determine forwarding destinations for data packets, and are also used to provide more advanced network Quality of Service (QoS) functions such as traffic shaping, traffic policing, rate limiting, and so on. More recently, CAM devices have been deployed in network environments to implement intrusion detection systems and to perform deep packet inspection tasks. A CAM device can be instructed to compare a selected portion of an incoming packet with CAM words stored in an array within the CAM device.
More specifically, a CAM device includes a CAM array having a plurality of CAM cells organized in a number of rows and columns. Each row of CAM cells, which can be used to store a CAM word, is coupled to a corresponding match line that indicates match results for the row. Each column of CAM cells is typically coupled to one or more data lines or data line pairs that can be used to drive data into a selected CAM row during write operations and/or for providing a search key to the CAM rows during compare operations. During a compare operation, the search key (e.g., the comparand word) is provided to the CAM array and compared with the CAM words stored therein. For each CAM word that matches the search key, a corresponding match line is asserted to indicate the match result, which is typically stored in a match latch associated with the matching CAM row. If one or more of the match lines are asserted, a match flag is asserted to indicate the match condition, and a priority encoder determines the match address or index of the highest priority matching (HPM) entry in the CAM array.
Because today's networking components process numerous different flows (e.g., groups of packets originating from a common source) at the same time, effective deployment of CAM devices in network environments favors the ability to quickly switch between multiple flows. To switch a CAM device between different flows, search operations for the currently active first flow (F1) are paused, and the match data (also referred to as state information) of the first flow is read from the match latches and stored in an external state memory. Then, the packets of the awaiting second flow (F2) are provided to the CAM device, and search operations are commenced for the second flow. To switch back to the first flow, search operations for the second flow (F2) are paused, the state information of the second flow F2 is saved in the external state memory, and then the state information of the first flow F1 is restored to the CAM array (e.g., loaded back into the array's match latches) from the external state memory.
The speed with which a CAM device can switch between different flows is typically dependent upon the number of active states (e.g., match values of “1” indicating a match condition) present in the CAM array's match latches. For example, some techniques for saving state information generate the HPM addresses of all active states using the CAM device's priority encoder, and then sequentially output the HPM addresses to the state memory. Other techniques read the state information from the CAM array's match latches in a serial fashion to the external state memory. However, as the number of active states in CAM devices increases, these prior techniques are becoming increasingly insufficient to maintain ever-faster network line speeds. For example, CAM devices configured to store a number of non-deterministic finite automaton (NFA) that embody an access control list (ACL) typically store many thousands of states, of which hundreds or even a few thousand can be active at any given time. For such CAM devices, the time required to transfer state information between the CAM device and an associated external state memory can be significant, during which search operations are not performed in the CAM device. As a result, switching between flows in such CAM devices has an increasingly adverse effect upon device throughput.
Accordingly, there is a need to improve the speed with which state information can be transferred between the CAM device and an associated external state memory.
Like reference numerals refer to corresponding parts throughout the drawing figures.